#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
using namespace std;
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> t;
        if (candidates.empty())return t;
        sort(candidates.begin(), candidates.end());
        return dfs(candidates, 0, target);

    }
    vector<vector<int>> dfs(vector<int>& candidates, int ks, int target)
    {
        vector<vector<int>> t,ans;
        if (ks>=candidates.size() || candidates[ks] > target)return t;
        
        if (candidates[ks] == target)
        {
            vector<int> tt;
            tt.push_back(target);
            ans.push_back(tt);
            return ans;

        }
        ans = dfs(candidates,ks + 1, target);
        t = dfs(candidates, ks, target - candidates[ks]);
        if (!t.empty())
        {
            for (int i = 0; i < t.size(); i++)
            {
                t[i].push_back(candidates[ks]);
                ans.push_back(t[i]);
            }
        }

        
        return ans;

    }
    
};
int main()
{
    Solution sol;
}